Problem algebry licealnej Tarskiego

Problem algebry licealnej Tarskiego (ang. High School Identities) – problem z zakresu logiki matematycznej postawiony przez Alfreda Tarskiego. Jego istotą jest pytanie o istnienie takich tożsamości zawierających dodawanie, mnożenie i potęgowanie dodatnich liczb całkowitych, których nie można udowodnić, korzystając jedynie z jedenastu aksjomatów dotyczących tych działań, zawartych w programie matematyki licealnej. Problem rozwiązał Alex Wilkie w roku 1980, pokazując, że takie tożsamości istnieją.

Przedstawienie problemu

Według Tarskiego poniższe 11 aksjomatów dodawania $(+),$ mnożenia $(\cdot )$ i potęgowania wchodziło w standardowy zakres nauczania w liceum:

1. $x+y=y+x,$
2. $(x+y)+z=x+(y+z),$
3. $x\cdot 1=x,$
4. $x\cdot y=y\cdot x,$
5. $(x\cdot y)\cdot z=x\cdot (y\cdot z),$
6. $x\cdot (y+z)=x\cdot y+x\cdot z,$
7. $1^{x}=1,$
8. $x^{1}=x,$
9. $x^{y+z}=x^{y}\cdot x^{z},$
10. $(x\cdot y)^{z}=x^{z}\cdot y^{z},$
11. $(x^{y})^{z}=x^{y\,\cdot \,z}.$

Aksjomaty te, czasem nazywane tożsamościami licealnymi, odpowiadają aksjomatom pierścieni wykładniczych.

Problem Tarskiego brzmi: czy istnieją tożsamości zawierające wyłącznie dodawanie, mnożenie oraz potęgowanie, które są prawdziwe dla każdej dodatniej liczby całkowitej, a których nie można dowieść, korzystając jedynie z aksjomatów 1–11?

Przykład twierdzenia możliwego do udowodnienia

Powyższe aksjomaty wydają się wyczerpywać wszystkie podstawowe fakty na temat rozważanych działań, dlatego intuicyjnie wydaje się, że dowolne stwierdzenia utworzone tylko za pomocą tych trzech operacji można udowodnić. Zupełnie inną kwestią jest długość dowodu, który nawet przy pozornie prostych twierdzeniach może być długi, jeśli rzeczywiście ograniczymy się wyłącznie do wymienionych jedenastu aksjomatów. Rozważmy następujący dowód, że $(x+1)^{2}=x^{2}+2\cdot x+1{:}$

$(x+1)^{2}$

$=(x+1)^{1+1}$

$=(x+1)^{1}\cdot (x+1)^{1},\quad (9)$

$=(x+1)\cdot (x+1),\quad (8)$

$=(x+1)\cdot x+(x+1)\cdot 1,\quad (6)$

$=x\cdot (x+1)+x+1,\quad (4),(3)$

$=x\cdot x+x\cdot 1+x\cdot 1+1,\quad (6),(3)$

$=x^{1}\cdot x^{1}+x\cdot (1+1)+1,\quad (8),(6)$

$=x^{1+1}+x\cdot 2+1,\quad (9)$

$=x^{2}+2\cdot x+1,\quad (4)$

Tam, gdzie nie jest to mylące, opuszczamy nawiasy na mocy aksjomatu 2.

Długość dowodu nie jest problematyczna. Dowód podobnej tożsamości tego typu, przykładowo $(x+y)^{100},$ zajmowałby o wiele więcej miejsca, ale nie zawierałby koncepcji innych, niż użyte wyżej.

Historia problemu

Listę jedenastu aksjomatów możemy znaleźć zapisaną jawnie w pracach Richarda Dedekinda, chociaż już dużo wcześniej były one szeroko znane wśród matematyków i uważane za oczywiste. Dedekind był pierwszym, który zwrócił uwagę, czy lista ta jest wyczerpująca, jeśli chodzi o użyteczne własności liczb całkowitych. Problem został ściśle postawiony jako dotyczący logiki i teorii modeli po roku 1960 przez Alfreda Tarskiego, a do roku 1980 był już znany jako „problem algebry licealnej Tarskiego”.

Rozwiązanie

W 1980 roku Alex Wilkie udowodnił, że nie każda tożsamość może zostać udowodniona przy pomocy powyższych aksjomatów. Dokonał tego, podając odpowiedni przykład. Korzystając z wprowadzonych przez siebie symboli funkcji odpowiadających wielomianom, które odwzorowują liczby dodatnie w liczby dodatnie, przeprowadził dowód tej tożsamości, a zarazem pokazał, że użyte funkcje w połączeniu z jedenastoma powyższymi aksjomatami są warunkiem koniecznym i wystarczającym do jego przeprowadzenia. Tożsamość jest postaci:

${\begin{aligned}&\left((1+x)^{y}+(1+x+x^{2})^{y}\right)^{x}\cdot \left((1+x^{3})^{x}+(1+x^{2}+x^{4})^{x}\right)^{y}\\={}&\left((1+x)^{x}+(1+x+x^{2})^{x}\right)^{y}\cdot \left((1+x^{3})^{y}+(1+x^{2}+x^{4})^{y}\right)^{x}.\end{aligned}}$

Zwykle oznacza się ją $W(x,y)$ i jest prawdziwa dla każdych dodatnich liczb całkowitych $x$ i $y,$ co można pokazać, rozkładając drugie wyrazy na iloczyn zawierający $(1-x+x^{2})^{xy}.$ Pomimo prawdziwości, tożsamości tej nie można udowodnić, używając jedenastu szkolnych aksjomatów.

W ujęciu intuicyjnym tożsamość jest niemożliwa do udowodnienia, bo aksjomaty licealne nie mogą zostać użyte do orzekania o wielomianie $1-x+x^{2}.$ Dyskusja o tym wielomianie i wyrazie $-x$ wymaga pojęcia negacji lub odejmowania, a te nie są obecne wśród aksjomatów szkolnych, a bez ich wykorzystania nie jest możliwe operowanie wymienionym wielomianem i dowodzenie jego własności. Wynik Wilkie’go wyrażony w sposób formalny w jego pracy pokazuje, że jedyną „luką” w aksjomatach licealnych jest właśnie niemożliwość operowania wielomianami o ujemnych współczynnikach.

Uogólnienia

Wilkie pokazał, że są twierdzenia o dodatnich liczbach całkowitych, które nie mogą zostać udowodnione przy użyciu powyższych jedenastu aksjomatów i wskazał, jakie dodatkowe informacje są potrzebne do przeprowadzenia ich dowodów. Korzystając z teorii Nevanlinna, można również dowieść, że przy ograniczeniu się do pewnych klas funkcji wykładniczych aksjomaty szkolne są wystarczające do udowodnienia każdego prawdziwego twierdzenia tego typu.

Innym, wciąż otwartym problemem wynikającym z rezultatu Wilkie’go, jest wskazanie najmniejszej algebry takiej, dla której $W(x,y)$ nie jest prawdziwa, jednak aksjomaty szkolne są. W roku 1985 wskazano odpowiednią algebrę 59-elementową. Od tej pory znaleziono też mniejsze algebry i znany jest fakt, że najmniejsza musi mieć 11 albo 12 elementów.

Bibliografia

• Stanley N. Burris, Karen A. Yeats, The saga of the high school identities, „Algebra Universalis” 52 no. 2–3, (2004), s. 325–342, MR2161657.
• Katarzyna Słomczyńska, High school identities, „Annales Universitatis Paedagogicae Cracoviensis Studia ad Didacticam Mathematicae Pertinentia” 7 (2015), s. 91–98.